NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part2/14126

Internet Message Format | 1996-08-05 | 3.4 KB

Path: anvil.ugrad.cs.ubc.ca!not-for-mail
From: [e-mail] (Kazimir Kylheku)
Newsgroups: comp.lang.c
Subject: Re: fast find algorithm
Date: 11 Apr 1996 12:07:25 -0700
Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
Message-ID: <[e-mail]>
References: <[e-mail]> <[e-mail]> <4k9ggs$[e-mail]> <4kbrg8$[e-mail]>
NNTP-Posting-Host: anvil.ugrad.cs.ubc.ca

In article <4kbrg8$[e-mail]>,
Pete Becker <[e-mail]> wrote:
 >In article <4k9ggs$[e-mail]>, [e-mail] says...
 >>
 >>Rogerio Brito ([e-mail]) wrote:
 >>: [e-mail] (Szu-Wen Huang) wrote:
 >>: >Falstaff ([e-mail]) wrote:
 >>: >...
 >>: >: Hashing is slightly slower than straight table lookup and can't be
 >>: >: used when you want to delete elements from your table.
 >>: >...
 >>
 >>: >Hashing can't be used when you want to delete elements?  Please explain.
 >>
 >>:         I think he is refering to elimination of the item of some
 >>:         table.   In  such  case,  you  should  change  your  hash
 >>:         function.  But if you don't have memory problems, you can
 >>:         simply ignore the  location  after  it  is "deleted".  Or
 >>:         depending on the implementation, you can simply unlink it
 >>:         from your linked list (if it is the case, of course).
 >>
 >>Hash tables need to have null entries so the search will know that
 >>the item doesn't exist.  I don't see why it is difficult to find
 >>the item to be deleted and overwrite it with the null entry.  As
 >>you said, it'll work on linked lists, but it will work also on array
 >>implementations.
 >
 >    It depends on what you use to resolve conflicting hash values for different
 >elements. If you resolve conflicts by rehashing, or by moving to the next
 >available entry in the hash array, or any other mechanism that uses the array
 >itself as the storage location for the conflicting value, then you can't delete
 >items, cause once you do there's no way to get to the ones that used to
 >conflict. The first one you try will map to your now-empty location, and it'll
 >look like it wasn't found.

This is false, and an obvious way gets around it. You place a ``tombstone''
marker in the deleted element rather than a vacant spot. I alrady mention this
in another posting to this thread, but I will repeat it anyway for clarity.

When you find the item to be deleted, you set a flag. The next time you search
for an element, you will see this flag and know that this is an empty spot, but
that you must keep searching! But when you search for a good place for a _new_
element, you _do_ stop at the tombstone: ``Ah, this spot is vacant! I can place
the new element there!''. You keep rehashing until you either find a tombstone
or you find a genuinely unused spot.

This is not perfect of course. Your hash table can get filled up with
tombstones that waste your time when searching for an element. Of course, the
check for a tombstone may be trivial with respect to your actual comparison
function between the lookup key and the element keys, so this consideration
might not be that important.

I'm sure that if you were to consult some ancient literature about hashing with
open addressing, you would find an analysis of the effect of tombstones on the
hash table performance and perhaps strategies to deal with them.
--